// 实现一个基本的计算器来计算一个简单的字符串表达式的值。

// 字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格  。

// 示例 1:

// 输入: "1 + 1"
// 输出: 2
// 示例 2:

// 输入: " 2-1 + 2 "
// 输出: 3
// 示例 3:

// 输入: "(1+(4+5+2)-3)+(6+8)"
// 输出: 23
// 说明：

// 你可以假设所给定的表达式都是有效的。
// 请不要使用内置的库函数 eval。

#include <stack>
#include <string>

using namespace std;

/* 栈和不反转字符串
解决这个问题需要理解以下内容：
    输入始终包含有效的字符串。
    加减法规则。
    括号中的优先含义。
    空格不影响输入表达式的计算。
解决 - 结合律的问题的一个分厂简单的方法就是使将 - 运算符看作右侧操作数的大小。一旦我们将 - 看作操作数的大小，则表达式将只剩下一个操作符。就是 + 运算符，而 + 是遵循结合律的。
时间复杂度：O(n)
空间复杂度：O(n)
*/
class Solution {
public:
    int calculate(string s) {
        int res{0}; // 记录压入栈的数字
        int temp{0}; // 记录当前数字，多位数
        int flag{1}; // 标志正负数，减号当做负数来处理（也可以理解成上一个+-号）
        stack<int> stk{};
        for (const char& c : s) {
            if (c >= '0' && c <= '9') {
                temp = 10 * temp + (c - '0');
            } else if (c == '+') {
                res += flag * temp;
                flag = 1;
                temp = 0;
            } else if (c == '-') {
                res += flag * temp;
                flag = -1;
                temp = 0;
            } else if (c == '(') {
                stk.push(res);
                stk.push(flag);
                flag = 1;
                res = 0;
            } else if (c == ')') {
                res += flag * temp; // 计算括号内的结果
                res *= stk.top(); // 获取入栈前的正负号
                stk.pop();
                res += stk.top(); // 加入入栈前的结果
                stk.pop();
                temp = 0; // )之前是数字，tempb不变
            }
        }
        //循环退出的时候，肯定最后一个是数字（合法表达式），要把result加上该数字，而且别忘了倒数第二位的正负号
        return res + flag * temp;
    }
};

/* 括号展开 + 栈
只有加减法，那么括号展开，把所有括号去掉，用真正的符号去一个一个累加
*/
class Solution {
public:
    int calculate(string s) {
        int result{};
        stack<int> ops{{1}}; // 栈里只存放 '+','-'，也就是1，-1
        int sign{1}; // 正负
        int n = s.size();
        int i{0};
        while (i < n) {
            char c = s[i];
            if (c == ' ') {
                ++i;
            } else if (c == '+') {
                sign = ops.top();
                ++i;
            } else if (c == '-') {
                sign = -ops.top();
                ++i;
            } else if (c == '(') {
                ops.push(sign);
                ++i;
            } else if (c == ')') {
                ops.pop();
                ++i;
            } else {
                long num{0};
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    num = num * 10 + s[i] - '0';
                    ++i;
                }
                result += sign * num;
            }
        }
        return result;
    }
};